#include <bits/stdc++.h>

using namespace std;

class Solution{
public:
    int countSub(vector<int>& nums){
        int n=nums.size(),ans=0;
        for(int i=2;i<n;i++){
            int x=nums[i-2], y=nums[i-1], z=nums[i];
            if((x+z)*2==y) ans++;
        }
        return ans;
    }
};

class Solution2 {
public:
    int countPathsWithXorValue(vector<vector<int>>& grid, int k) {
        const int MOD = 1e9+7;
        int mx = 0;
        for (auto& row : grid) {
            sort(row.begin(),row.end(), greater());
//            mx = max(mx, ranges::max(row));
            mx=max(mx, row[0]);
        }
        int u = 1 << __bit_width((unsigned) mx);
        if (k >= u) {
            return 0;
        }

        int m = grid.size(), n = grid[0].size();
        vector memo(m, vector(n, vector<int>(u, -1)));
        function<int(int,int,int)> dfs=[&](int i,int j, int x) -> int{
//        auto dfs = [&](this auto&& dfs, int i, int j, int x) -> int {
            if (i < 0 || j < 0) {
                return 0;
            }
            int val = grid[i][j];
            if (i == 0 && j == 0) {
                return x == val;
            }
            int& res = memo[i][j][x]; // 注意这里是引用
            if (res != -1) {
                return res;
            }
            return res = (dfs(i, j - 1, x ^ val) + dfs(i - 1, j, x ^ val)) % MOD;
        };
        return dfs(m - 1, n - 1, k);
    }
};


// 区间重叠 n*log(n)
class Solution3{
public:
    bool checkValidCuts(int n, vector<vector<int>>& rectangles) {
        auto gao=[&](vector<pair<int,int>> &vec){
            sort(vec.begin(),vec.end());
            int ret=0,R=-1e9;
            for(pair<int,int> p: vec){
                if(p.first>=R) ret++;
                R=max(R,p.second);
            }
            return ret;
        };
        vector<pair<int,int>> vec;
        for(auto &rect: rectangles) vec.push_back({rect[0], rect[2]});
        if(gao(vec)>=3) return true;
        vec.clear();
        for(auto &rect: rectangles) vec.push_back({rect[1], rect[3]});
        return gao(vec)>=3;
    }
};

class Solution4 {
    int comb2(int num) {
        return num * (num - 1) / 2;
    }

public:
    int subsequencesWithMiddleMode(vector<int>& nums) {
        int n = nums.size();
        long long ans = 1LL * n * (n - 1) * (n - 2) * (n - 3) * (n - 4) / 120; // 所有方案数

        vector<int> a(nums);
        sort(a.begin(),a.end());
        a.erase(unique(a.begin(), a.end()), a.end()); // 去重
        for (int &x : nums) {
            x = lower_bound(a.begin(),a.end(), x) - a.begin();
        }

        vector<int> pre(a.size()), suf(a.size());
        for (int x : nums) {
            suf[x]++;
        }
        // 枚举 x，作为子序列正中间的数
        for (int left = 0; left < n - 2; left++) {
            int x = nums[left];
            suf[x]--;
            if (left > 1) {
                int right = n - 1 - left;
                int pre_x = pre[x], suf_x = suf[x];
                // 不合法：只有一个 x
                ans -= 1LL * comb2(left - pre_x) * comb2(right - suf_x);
                // 不合法：只有两个 x，且至少有两个 y（y != x）
                for (int y = 0; y < a.size(); y++) {
                    if (y == x) {
                        continue;
                    }
                    int pre_y = pre[y], suf_y = suf[y];
                    // 左边有两个 y，右边有一个 x，即 yy x xz（z 可以等于 y）
                    ans -= 1LL * comb2(pre_y) * suf_x * (right - suf_x);
                    // 右边有两个 y，左边有一个 x，即 zx x yy（z 可以等于 y）
                    ans -= 1LL * comb2(suf_y) * pre_x * (left - pre_x);
                    // 左右各有一个 y，另一个 x 在左边，即 xy x yz（z != y）
                    ans -= 1LL * pre_y * suf_y * pre_x * (right - suf_x - suf_y);
                    // 左右各有一个 y，另一个 x 在右边，即 zy x xy（z != y）
                    ans -= 1LL * pre_y * suf_y * suf_x * (left - pre_x - pre_y);
                }
            }
            pre[x]++;
        }
        return ans % 1'000'000'007;
    }
};

int main(){
    vector<int> nums={1,2,1,4,1};
    Solution s; cout<<s.countSub(nums)<<endl;

    vector<vector<int>> grid={{2,1,5},{7,10,0},{12,6,4}};
    Solution2 s2; cout<<s2.countPathsWithXorValue(grid, 4)<<endl;

    vector<vector<int>> rect={{1,0,5,2},{0,2,2,4},{3,2,5,3},{0,4,4,5}};
    Solution3 s3; cout<<s3.checkValidCuts(5, rect)<<endl;

    Solution4 s4; vector<int> nums4={1,1,1,1,1,1}; cout<<s4.subsequencesWithMiddleMode(nums4)<<endl;

    return 0;
}